In semiconductor memory testing environments, it is often useful to generate random patterns of numbers in order to facilitate the simulation of real-world situations. However, the generation of genuinely random numbers is exceedingly complex and, in most instances, genuinely random numbers are not necessary. For most applications, a pseudo-random sequence of numbers will suffice. Pseudo-random sequences are finite sequences generated by a deterministic process but statistically indistinguishable from a random sequence. Pseudo-random numbers are used in many applications, not only because genuinely random numbers are very difficult to generate, but also because the lack of reproducibility in genuinely random numbers makes the validation of programs or applications that use random numbers extremely difficult.
Methods for generating a sequence of pseudo-random numbers are known in the art. A function called a generator is defined such that, when applied to a number, it yields the next number in the pseudo-random sequence. While any type of pseudo-random number generator can be used, for simplicity, and because it is the most commonly used generator, a linear congruential generator (LCG) is discussed below.
An LCG generates a deterministic, non-repeating, pseudo-random sequence. A subsequent number in the sequence (Xn) is generated from the current number (Xn−1) through the following equation:Xn=(aXn−1+c)mod(m)  (1)where Xn−1 is the (n−1)th number of the sequence; a is a multiplier; c is an additive constant; m is the modulus. An initial value X0 also makes up the LCG. X0 is an initial value of Xn−1 to start the sequence and is usually any positive odd integer. When iterated, each resultant value of Xn is then a member of the psuedo-random sequence. Because of the reduction mod (m) operation, Xn will always fall in the range (0 through m−1) and, as a result, will eventually repeat itself. The length of the unrepeated sequence is called the period of the generator. A good generator is one with a long period and no discernible correlation between elements of the sequence.
The “seed” values are the values chosen for X0, a, c, and m. The seed values are chosen to make the sequence look as random as possible. An exemplary set of seed values is:X0=any positive odd integera=16807m=231−1 (or some other large prime number)c=0
The generator described in Equation 1 with the above seed values has a period of m−1, that is, 231−2 for m=231−1.
When using a binary system, such as a processor-based system, the seed values are often simplified even further in order to make the computation of the pseudo-random sequence faster. The following seed values provide a simplification of Equation 1 that sacrifices the period of the generator in favor of faster computation:X0=any positive odd integera=8z+5 (z is any positive integer)m=2e (e is any positive integer)c=0;so that equation 1 then becomesXn=(aXn−1)mod(m)  (2)
By using the above-identified exemplary seed values, the addition of c is eliminated, and the modulus of the product aXn−1 can be more quickly determined. That is, when using a binary system, since m is a power of 2, regardless of what integer value is chosen for e, the result of the modulus of m will be the e least significant bits of the product of the multiplier, a, and the (n−1)th number of the sequence, Xn−1. For example, if e=4, then aXn−1 mod (m) is simply the 4 least significant bits of aXn−1. Thus, using a binary system eliminates the necessity of actually performing a lengthy reduction mod m calculation. By using fewer operations, the processing time necessary to determine Xn in a binary system can be reduced.
Although simpler, the binary system approach described above is not ideal because the value for m, by definition, is not prime. Since the value of m is not prime, the period of the generator is reduced from a maximum of m−1 down to 2e−2 or m/4. In addition, since m is a power of 2, the low order bits of each of the generated numbers are not random. Specifically, depending on the seed values, bits 0 and 1 are fixed for all numbers generated and bits 2 and 3 occur in a cyclical pattern.
For example, if the above formula is used with seed values of X0=1; a=5; m=16 (e=4); and c=0, the following sequence would be generated: 1, 5, 9, 13, 1, 5, 9, 13, 1 . . . . This sequence in binary form appears as follows:
TABLE 1XnXnNIntegerBinary0100011501012910013131101
As can be seen from Table 1, the two least significant bits for each value of Xn (i.e., for each number generated in the sequence of pseudo-random numbers) are fixed at “01” and the two most significant bits cycle through the binary values 00, 01, 10, 11, 00, 01, 10, 11 . . . (i.e., decimal values 0, 1, 2, 3, 0, 1, 2, . . . ). Thus, the random nature of the sequence generated by the LCG is compromised through implementing simpler seed values with a binary system. While this is a simplified example, a similar pattern for bits 0-3 would occur when using the simplified seed values associated with a binary system, as described above for Equation 2.
After the above-described deterministic, non-repeating, pseudo-random numbers are generated in software using an LCG, they must be transmitted to another location in a memory circuit where memory locations are being tested. This generation in software and then transportation via hardware to a memory location is a relatively slow process.
For example, when a memory device is being tested in a computer, the speed with which the software can get the processor to generate the pseudo-random addresses and move them to a location to be used for testing are the limiting factors for implementing the LCG in software. Thus, it is desirable to develop a system for speedily generating a sequence of deterministic, non-repeating, pseudo-random numbers, to assemble memory addresses from the sequence of pseudo-random numbers and to use the assembled addresses in a memory testing environment.